package 系统复习.面试题.矩阵;

/**
 * 给定两个 稀疏矩阵 ：大小为 m x k 的稀疏矩阵 mat1 和大小为 k x n 的稀疏矩阵 mat2 ，
 * 返回 mat1 x mat2 的结果。你可以假设乘法总是可能的。
 */
public class L311 {

    public int[][] multiply(int[][] mat1, int[][] mat2) {

        int n = mat1.length;
        int m = mat2[0].length;
        // k: 每一项需要计算的元素个数
        int k = mat1[0].length; // a的列数同时也是b的行数
        int[][] ans = new int[n][m];

        for (int i = 0; i < n; i++) { // 行
            for (int c = 0; c < k; c++) { // 每一项需要累加的个数
                if (mat1[i][c] == 0) { // 即: 矩阵A中第C个0元素项目, 没有必要参与后面的累加了
                    continue; // c++, 跳到下一个不为零的 a[i][c]上
                }
                for (int j = 0; j < m; j++) {
                    // 依然累加了a中0的项目
                    ans[i][j] += mat1[i][c] * mat2[c][j];
                }
            }
        }
        return ans;

    }

}
